SP27942 PROD1GCD - Product it again

并不会有更好的阅读体验 甚至你在机房还访问不了

i=1nj=1m(i,j)\prod_{i=1}^n\prod_{j=1}^m (i,j)

d=1min(n,m)di=1nj=1m[(i,j)=d]\prod_{d=1}^{\min(n,m)} d^{\sum_{i=1}^n\sum_{j=1}^m [(i,j)=d]}

d=1min(n,m)dk=1min(nd,md)μ(k)nkdmkd\prod_{d=1}^{\min(n,m)} d^{\sum_{k=1}^{\min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)} \mu(k) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor}

d=1min(n,m)ddk=1min(n,m)μ(k)nkdmkd\prod_{d=1}^{\min(n,m)} d^{\sum_{dk=1}^{\min(n,m)} \mu(k) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor}

T=1min(n,m)dTdμ(Td)nTmT\prod_{T=1}^{\min(n,m)} \prod_{d|T}d^{\mu(\frac{T}{d}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor}

f(n)=dn(nd)μ(d)f(n)=\prod_{d|n} (\frac{n}{d})^{\mu(d)} , 虽然不是积性函数,仍考虑线性筛。

首先考虑一个式子:

dnxμ(d)=xdnμ(d)=x[n=1]\prod_{d|n} x^{\mu(d)}=x^{\sum_{d|n} \mu(d)} = x^{[n=1]}

然后有:

  1. i=1i=1f(i)=1f(i)=1
  2. iprimei\in primef(i)=iμ(1)×1μ(i)=i1×11=if(i)=i^{\mu(1)} \times 1^{\mu(i)}=i^1\times 1^{-1}=i
  3. ipi\not| pf[i×p]=1f[i \times p]=1
  4. ipi|pf[i×p]=f[i]f[i \times p]=f[i]

3344 点可以展开后利用上式化简。

其中 ppi×pi \times p 的最小质因子。

ps. 整除分块中 l1l-1 可能为 00 , 为了方便令 f(0)=1f(0)=1

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 1e7 , Mod = 1e9 + 7;

int Quick_pow( int x , int po , int p = Mod ) {
	int Ans = 1;
	for( ; po ; po >>= 1 , x = 1ll * x * x % p )
		if( po & 1 ) Ans = 1ll * Ans * x % p;
	return Ans;
}
int Inv( int x , int p = Mod ) {
	return Quick_pow( x , p - 2 );
}

int prn , prime[ MAXN + 5 ] , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
	f[ 0 ] = 1 , f[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) { prime[ ++ prn ] = i , f[ i ] = i; }
		for( int j = 1 ; j <= prn && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) {
				f[ i * prime[ j ] ] = f[ i ];
				break;
			}
			f[ i * prime[ j ] ] = 1;
		}
	}
	for( int i = 2 ; i <= MAXN ; i ++ ) f[ i ] = 1ll * f[ i - 1 ] * f[ i ] % Mod;
}

int Solve( int n , int m ) {
	int Ans = 1 , k = min( n , m );
	for( int l = 1 , r ; l <= k ; l = r + 1 ) {
		r = min( n / ( n / l ) , m / ( m / l ) );
		Ans = 1ll * Ans * Quick_pow( 1ll * f[ r ] * Inv( f[ l - 1 ] ) % Mod , 1ll * ( n / l ) * ( m / l ) % ( Mod - 1 ) ) % Mod;
	}
	return Ans;
}

int t , n , m;
int main( ) {
	sieve( );
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d %d",&n,&m);
		printf("%d\n", Solve( n , m ) );
	}
	return 0;
}